package leetcode.code0479;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution479 implements IDebug {

//	1 9 81
//	2 99 9801
//	3 999 998001
//	4 9999 99980001
//	5 99999 9999800001
//	6 999999 999998000001
//	7 9999999 99999980000001
//	8 99999999 9999999800000001

	public int largestPalindrome(int n) {
		int largest = (int) Math.pow(10, n) - 1;// n位最大数
		long max = (long) Math.pow(largest, 2);// 平方最大值
		for (int i = largest - 1; i > 0; i--) {
			long num = this.palindrome(i);// i同i镜像组成的回文数
			for (long ans = largest; num <= max && ans * ans >= num; ans--) {
				if (num % ans == 0) {
//					System.out.println(num + " = " + ans + " * " + num / ans);
					return (int) (num % 1337);
				}
			}
		}
		return 9;
	}

	private long palindrome(int num) {
		long mirror = 0;
		long ans = num;
		while (num > 0) {
			mirror = mirror * 10 + num % 10;
			ans *= 10;
			num /= 10;
		}
		return ans + mirror;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(987, this.largestPalindrome(2));
	}

	@Override
	public void debug2() {
		HelpDebug.compare(677, this.largestPalindrome(5));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {

	}

	public static void main(String[] args) {
		Solution479 so = new Solution479();
//		so.debug2();
//		so.debug1();
		for (int i = 1; i < 9; i++) {
			int n = so.largestPalindrome(i);
			System.out.println(n);
		}

	}

}
